package dp.base;

public class Solution_70 {

    int[] memo;

    /**
     * 容易犯错的是这里的数组初始长度的设置
     */
    public int climbStairs(int n) {
        memo = new int[n + 1];
        return dfs(n);
    }

    private int dfs(int i) {
        if (i == 0 || i == 1)
            return 1;
        if (memo[i] != 0)
            return memo[i];
        return memo[i] = dfs(i - 1) + dfs(i - 2);
    }
}
